class CharTrie:
	"""docstring for CharTrie"""
	def __init__(self):
		self.children = None
		self.value = None

	def insert(self,key:str,value=None):
		i = 0
		t = self
		while i < len(key):
			k = key[i]
			child_index = ord(k)-ord('a') # ord()方法将char转换成ASCII值，反过来有方法chr()
			# print("child_index:" + str(child_index))
			if t.children is None:
				t.children = [None]*26
			t.children[child_index] = CharTrie()
			i += 1
			t = t.children[child_index]
		t.value = value
		return t

	def lookup(self,key:str):
		i = 0 # 字符串下标
		t = self
		# 循环检查children列表
		while i < len(key):
			if t.children is None:
				return None
			else:
				k = key[i]
				t = t.children[ord(k)-ord('a')] # 进入下一层
				if t is None:
					break
				i += 1
		return t

	# 递归形式的查找 	
	def lookup_recursive(self,key:str,strindex=0):
		if strindex == len(key) or self is None:
			return self
		child = self.children[ord(key[strindex])-ord('a')]
		return child.lookup_recursive(key,strindex+1) if child is not None else None


if __name__ == '__main__':
	tree = CharTrie()
	node = tree.insert('animal','monkey')
	print(node.value)
	node2 = tree.insert('telephone','apple')
	print(node2.value)
	# 查找 
	rt = tree.lookup('animal')
	print(rt.value if rt is not None else None)
	rt_recursive = tree.lookup_recursive('telephone')
	print(rt_recursive.value if rt is not None else None)

	res = tree.lookup("howareyou")
	print(res.value  if res is not None else None)

